package cxydmmszl.chapter05.t098;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * 回文最少分割
 * <li style="color: green;">Desc</li>
 * 给定一个字符串，返回把 str 全部切割成回文串的最少切割数。
 * <li style="color: green;">Input</li>
 * 输出包含一行字符串，代表 str(1≤length(str)≤5000)。
 * <li style="color: green;">Output</li>
 * 输出一个整数，代表把 str 全部切割成回文串的最小切割数。
 * <li style="color: blue;">Link</li> CD135
 *
 * @author habitplus
 * @since 2021-10-10 14:43
 */
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();

        int ans = minCut(str);
        System.out.println(ans);
    }

    private static int minCut(String str) {
        if (str == null || str.length() < 2) return 0;

        char[] chs = str.toCharArray();
        int n = chs.length;
        // dp[i] 表示 str[i,n-1] 至少需要切割多少次，才能把它全部切成回文子串
        int[] dp = new int[n + 1];
        // p[i][j] = true 表示 str[i,j] 整体是一个回文串，否则不是
        boolean[][] p = new boolean[n][n];
        dp[n] = -1;
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = Integer.MAX_VALUE;
            // 枚举 [i,n-1] 的每个位置，找出最小值
            for (int j = i; j < n; j++) {
                // 假设 str[i,j] 作为一个回文串，
                // 那个整个子串 str[i,n-1] 的分割数就是 dp[j+1] + 1
                if (chs[i] == chs[j] && (j - i < 2 || p[i + 1][j - 1])) {
                    p[i][j] = true;
                    dp[i] = Math.min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        return dp[0];
    }
}
